ON THE UD FILTER IMPLEMENTATION METHODS

Tsyganova Yuliya Vladimirovna, Candidate of physical and mathematical sciences, associate professor, sub-department of information technologies, Ulyanovsk State University
(42 Lva Tolstogo street, Ulyanovsk, Russia), jvt.ulsu@gmail.com

[519.254+519.654]:629.5.05

Background. The Kalman filter (KF) is a mathematical tool that has won wide popularity among professionals in the field of estimation and control. However, it has a drawback – instability in respect to machine round off errors in its practical implementation on a computer. It is well known that the problem of machine round off errors is unavoidable due to the limited machine width of real floating-point numbers. However, one can significantly reduce the effect of round off errors in algebraically equivalent Kalman filter implementations (the so-called numerically efficient implementations). They are based on different mathematical factorization methods of the estimation error covariance matrices involved in the filter equations. The aim of the paper is to study the basic UD implementation methods of the discrete Kalman Filter with improved computational properties in comparison with the standard KF implementation, as well as the construction of the new extended orthogonal form of the UD filter which should have the following properties: robustness of computations against round off errors; lack of the square-root operation; deliverance from matrix inverse operation on each stage of the algorithm; compact and convenient orthogonal form of the UD filter.
Materials and methods. The paper is based on the UD filter implementation methods. The first UD imple-mentation of the KF was the Bierman’s sequential algorithm. Matrix orthogonal algorithms are the most modern numerically efficient KF implementations. The approach to the construction of the square-root orthogonal algorithms was proposed by Kailath and it is used in the paper to construct a new form of the extended orthogonal UD filter. Results. In the paper the existing implementation methods of UD filter have been investigated. The orthogonal forms of the UD filter are the most computationally efficient and suitable for implementation in modern computer systems. A new form of the extended orthogonal UD filter, which has a number of advantages in comparison with others, has been proposed.
Conclusions. The sequential and orthogonal forms of the UD algorithms are the most numerically efficient implementations of the discrete Kalman filter. Their benefits are: 1) robustness of computations against round off errors; 2) lack of the square-root operation; 3) deliverance from matrix inverse operation on each stage of the algorithm; 4) compact and convenient orthogonal form of the UD filter. The numerical experiments have shown the efficiency of the proposed new form of extended orthogonal UD filter and its computations robustness against round off errors while dealing with ill-conditioned tasks.

stochastic discrete linear systems, optimal discrete filtering, the Kalman filter, robust implementations of the discrete filter, the UD filter.

1. Kalman R. E. Trans. of the ASME–Journal of Basic Engineering. 1960, vol. 82, Series D. pp. 35–45.
2. Potter J. E., Stern R. G. Proceedings of 1963 AIAA Guidance and Control Conference. New York: AIAA, 1963.
3. Bierman G.J. Factorization methods for discrete sequential estimation. New York: Academic Press,1977,255 p.
4. Maybeck P. S. Stochastic models, estimation and control, Vol.1. New York: Academic Press, Inc.,1979,423 p.
5. Kailath T., Sayed A. H., Hassibi B. Linear estimation. New Jersey: Prentice Hall, 2000, 854 p.
6. Grewal M. S., Andrews A. P. Kalman filtering: theory and practice. New Jersey: Prentice-Hall, 2001, 410 p.
7. Ogarkov M. A. Metody statisticheskogo otsenivaniya parametrov sluchaynykh protsessov [Methods of statistical estimation of stochastic process parameters]. Moscow: Energoatomizdat, 1990, 208 p.
8. Semushin I. V., Tsyganova Yu. V., Kulikova M. V. et al. Adaptivnye sistemy fil'tratsii, upravleniya i obnaruzheniya: kollektivnaya monografiya [Adaptive systems of filtration, control and detection: collaborative monograph]. Ulyanovsk: Izd-vo UlGU, 2011, 298 p.
9. Semushin I. V. Vychislitel'nye metody algebry i otsenivaniya: uchebnoe posobie [Computational methods of algebra and estimation: tutorial]. Ul'yanovsk: UlGTU, 2011, 366 p.
10. Bierman G. J., Thornton C. L. Automatica. 1977, vol. 13, pp. 23–35.
11. Fomin V. N. Rekurrentnoe otsenivanie i adaptivnaya fil'tratsiya [Recurrent estimation and adaptive filtration]. Moscow: Nauka, 1984, 288 p.
12. L'yung L. Identifikatsiya sistem. Teoriya dlya pol'zovatelya: per. s angl. [System identification. Theory for users: translation from English]. Moscow: Nauka, 1991, 432 p.
13. Saridis Dzh. Samoorganizuyushchiesya stokhasticheskie sistemy upravleniya: per. s angl. [Self-organizing stochastic systems of control: translation from English]. Moscow: Nauka, 1980, 400 p.
14. Mosca E. Optimal, predictive and adaptive control. New Jersey: Prentice-Hall, Inc., 1995, 477 p.
15. Thornton C. L. Triangular Covariance Factorizations for Kalman Filtering: Ph. D. Thesis. University of California at Los Angeles, School of Engineering, 1976.
16. Park P., Kailath T. IEEE Trans. Automat. Control. 1995, vol. 40, no. 5, pp. 895–899.
17. Jover J. M., Kailath T. Automatica. 1986, vol. 22, no. 1, pp. 43–57.
18. Hotop H.-J. Parallel Computing. 1989, no. 12, pp. 233–247.
19. Gentleman W. M. J. Inst. Math. Appl. 1973, no. 12, pp. 329–336.
20. Dyer P., McReynolds S. J. Optim. Theory Appl. 1969, no. 3, pp. 444–459.
21. Verhaegen M., P. Van Dooren IEEE Trans. Automat. Contr. 1986, vol. 31, no. 10, pp. 907–917.
22. Tsyganova Yu. V. Avtomatika i telemekhanika [Automatc and telemechanics]. 2011, no. 9, pp. 142–160.
23. Tsyganova Yu. V., Kulikova M. V. Avtomatika i telemekhanika [Automatc and telemechanics]. 2012, no. 6, pp. 34–51.
24. Tsyganova J.V., Kulikova M.V. IEEE Transactions on Automatic Control.2013,vol.58, no.11, pp.2938–2944.
25. Björck Å. BIT. 1967, vol. 7, pp. 1–21.
26. Jordan T. L. Math. Comp. 1968, vol. 22, pp. 579–588.